#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int kMaxN = 1200;
const long long kInf = 1e18;

vector<pair<int, int>> g[kMaxN];
long long dist[kMaxN][kMaxN];
int s[kMaxN], now_s[kMaxN];

void Dijkstra(int n) {
  priority_queue<pair<long long, int>> pq;

  for (int i = 1; i <= n; i++) {
    fill(dist[i], dist[i] + n + 1, kInf);
  }

  fill(now_s, now_s + n + 1, kMaxN);
  dist[1][1] = 0;
  pq.emplace(-dist[1][1], 1 * (n + 1) + 1);
  while (!pq.empty()) {
    long long d = -pq.top().first;
    int u = pq.top().second / (n + 1), s_num = pq.top().second % (n + 1);

    pq.pop();
    if (dist[u][s_num] != d || now_s[u] <= s[s_num]) {
      continue;
    }
    now_s[u] = s[s_num];
    // cout << "now: " << u << "," << s_num << ": " << d << endl;
    for (const pair<int, int>& e : g[u]) {
      int v = e.first;
      int next_s = s[s_num] > s[v] ? v : s_num;

      if (dist[v][next_s] > d + e.second * s[s_num]) {
        dist[v][next_s] = d + e.second * s[s_num];
        // cout << v << "," << next_s << ": " << dist[v][next_s] << endl;
        pq.emplace(-dist[v][next_s], v * (n + 1) + next_s);
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;

  for (cin >> t; t; t--) {
    int n, m;

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
      g[i].clear();
    }
    for (int i = 0; i < m; i++) {
      int u, v, w;

      cin >> u >> v >> w;
      g[u].emplace_back(v, w);
      g[v].emplace_back(u, w);
    }
    for (int i = 1; i <= n; i++) {
      cin >> s[i];
    }

    Dijkstra(n);

    long long ans = dist[n][1];
    for (int i = 2; i <= n; i++) {
      ans = min(dist[n][i], ans);
    }
    cout << ans << "\n";
  }
  return 0;
}